package kingAI.calc;

import kingAI.calc.util.*;

/**
 * Probable taken card/trick amount calculator for a single suit hand.
 * Standard trump rules govern. This suit is the trump.
 * 
 * @author Equilibrium
 * @version 1.0
 */
public class SingleSuitCalculator {
	private int totalSituations;
	
	private int emptyRegionQuantity;
	private int[] emptyRegionCardQuantities;
	//TODO: change empty regions begin/end with mechanisms into more efficient ones
	private int[] emptyRegionsBeginWith;
	private int[] emptyRegionsEndWith;
	
	private double[] cardPossessionProbabilities;
	private boolean[] cards;
	private int cardsAmount;
	
	private CalculationType calculationType;
	
	/**
	 * Probable amount of taken cards after calculation.
	 */
	public double probableAmountOfTakenCards;
	
	/**
	 * Probable amount of taken tricks after calculation.
	 */
	public double probableAmountOfTakenTricks;
		
	/**
	 * Probable amount of given cards after calculation of cards taken from another suit.
	 */
	public double probableAmountOfGivenCards;
	
	/**
	 * Probable amount of given tricks after calculation of tricks taken from another suit.
	 */
	public double probableAmountOfGivenTricks;
	
	/**
	 * Constructs a new calculator.
	 * 
	 * @param cardPossessionProbabilities Possession probability of this suit's cards. All are 0.0~1.0
	 * @param calculationType Taken cards probability calculation type of these cards from a single suit.
	 */
	public SingleSuitCalculator(double[] cardPossessionProbabilities, CalculationType calculationType){
		probableAmountOfTakenCards=0.0;
		probableAmountOfTakenTricks=0.0;
		probableAmountOfGivenCards=0.0;
		probableAmountOfGivenTricks=0.0;
		cardsAmount=0;
		
		this.calculationType = calculationType;
		this.cardPossessionProbabilities = cardPossessionProbabilities;
		
		cards = new boolean[15];
		for(int i=2;i<15;i++)
			if(cardPossessionProbabilities[i]!=0.0){
				cards[i]=true;
				cardsAmount++;
			}
		
		//empty region quantity calculation
		emptyRegionQuantity=0;
		boolean currentCardGroup = true;
		for(int i=2;i<15;i++){
			if(currentCardGroup&&(!cards[i]))
				emptyRegionQuantity++;
			currentCardGroup=cards[i];
		}
		
		//calculation of card amounts in empty regions and card numbers regions begin and end with
		emptyRegionsBeginWith = new int[emptyRegionQuantity];
		emptyRegionsEndWith = new int[emptyRegionQuantity];
		emptyRegionCardQuantities = new int[emptyRegionQuantity];
		
		for(int i=2,j=0;i<15;i++)
			if(cards[i])
				continue;
			else{
				emptyRegionsBeginWith[j]=i;
				for(;i<15&&(!cards[i]);i++)
					emptyRegionCardQuantities[j]++;
				emptyRegionsEndWith[j]=i-1;
				j++;
			}
	}

	/**
	 * Calculates recursively the probable amount of tricks taken in this distribution (if played a negative contract).
	 * Calculates recursively the average of the worst case and the best case.
	 * 
	 * @param cards Possession of cards.
	 * @param playersCardsAmounts Card amounts of all other players in all regions. 1st index is players, 2nd index is regions.
	 * @param takenCards Number of cards taken currently.
	 * @return Probable number of tricks taken.
	 */
	private double takenTrickProbability(boolean[] cards, int[][] playersCardsAmounts, double takenTricks){		
		//finding the current lowest card
		boolean[] thisCards = ArrayOperations.copy(cards);
		
		int lowestCard;
		for(lowestCard=2;lowestCard<15;lowestCard++)
			if(thisCards[lowestCard])
				break;
		if(lowestCard==15)
			return takenTricks;
		
		thisCards[lowestCard]=false;
		
		int[][] playersCardsAmountsBestCase = ArrayOperations.copy(playersCardsAmounts);
		int[][] playersCardsAmountsWorstCase = ArrayOperations.copy(playersCardsAmounts);
		boolean taken, otherPlayersHaveNoCards=true;
		double tricksTakenBestCase=0.0;
		
		//best case calculation
		taken=true;
		for(int i=0;i<3;i++)
			for(int j=0;j<playersCardsAmountsBestCase[0].length;j++)
				if(playersCardsAmountsBestCase[i][j]>0){
					if(emptyRegionsBeginWith[j]>lowestCard)
						taken=false;
						
					playersCardsAmountsBestCase[i][j]--;
					otherPlayersHaveNoCards=false;
					break;
				}
		
		//return if other players have no cards
		if(otherPlayersHaveNoCards)
			return takenTricks;
		
		if(taken)
			tricksTakenBestCase=cardPossessionProbabilities[lowestCard];
		else
			tricksTakenBestCase=0.0;
		
		//worst case calculation
		double tricksTakenWorstCase=0.0;
		taken=true;
		int regionToPlay;
		
		for(int i=0;i<3;i++){
			regionToPlay=-1;
			for(int j=0;j<playersCardsAmountsWorstCase[0].length && emptyRegionsEndWith[j]<lowestCard;j++)
				if(playersCardsAmountsWorstCase[i][j]>0)
					regionToPlay=j;
			
			if(regionToPlay==-1)
				for(int j=playersCardsAmountsWorstCase[0].length-1;j>=0 && emptyRegionsBeginWith[j]>lowestCard;j--)
					if(playersCardsAmountsWorstCase[i][j]>0){
						taken=false;
						regionToPlay=j;
						break;
					}
				
			if(regionToPlay!=-1)
				playersCardsAmountsWorstCase[i][regionToPlay]--;
		}		
		
		if(taken)
			tricksTakenWorstCase=cardPossessionProbabilities[lowestCard];
		else
			tricksTakenWorstCase=0.0;
		
		return takenTricks + (takenTrickProbability(thisCards,playersCardsAmountsBestCase,tricksTakenBestCase)+
				takenTrickProbability(thisCards,playersCardsAmountsWorstCase,tricksTakenWorstCase))/2;
	}
	
	
	/**
	 * Calculates recursively the probable amount of cards taken from one other suit in this distribution (if played a negative contract).
	 * Calculates recursively the average of the worst case and the best case.
	 * 
	 * @param cards Possession of cards.
	 * @param playersCardsAmounts Card amounts of all other players in all regions. 1st index is players, 2nd index is regions.
	 * @param takenCards Number of cards taken currently. Call with 0.
	 * @return Probable number of cards taken.
	 */
	private double takenCardFromOtherSuitProbability(boolean[] cards, int[][] playersCardsAmounts, double takenCards){		
		//finding the current lowest card
		boolean[] thisCards = ArrayOperations.copy(cards);
		
		int highestCard;
		for(highestCard=14;highestCard>1;highestCard--)
			if(thisCards[highestCard])
				break;
		if(highestCard==1) //if there are no cards in hand
			return takenCards;
		
		thisCards[highestCard]=false;
		
		int[][] playersCardsAmountsBestCase = ArrayOperations.copy(playersCardsAmounts);
		int[][] playersCardsAmountsWorstCase = ArrayOperations.copy(playersCardsAmounts);
		boolean taken;
		
		//best case calculation
		double cardsTakenBestCase=3.0;
		taken=true;
		
		for(int i=0;i<3;i++)
			for(int j=0;j<playersCardsAmountsBestCase[0].length;j++)
				if(playersCardsAmountsBestCase[i][j]>0){
					if(emptyRegionsBeginWith[j]>highestCard)
						taken=false;
						
					playersCardsAmountsBestCase[i][j]--;
					cardsTakenBestCase--;
					break;
				}
		
		if(cardsTakenBestCase==3.0)//return if other players have no cards left
			return takenCards;
		
		if(!taken)
			cardsTakenBestCase=0.0;
		
		//worst case calculation
		double cardsTakenWorstCase=3.0;
		taken=true;
		int regionToPlay;
		
		for(int i=0;i<3;i++){
			regionToPlay=-1;
			for(int j=0;j<playersCardsAmountsWorstCase[0].length && emptyRegionsEndWith[j]<highestCard;j++)
				if(playersCardsAmountsWorstCase[i][j]>0)
					regionToPlay=j;
			
			if(regionToPlay==-1)
				for(int j=playersCardsAmountsWorstCase[0].length-1;j>=0 && emptyRegionsBeginWith[j]>highestCard;j--)
					if(playersCardsAmountsWorstCase[i][j]>0){
						taken=false;
						regionToPlay=j;
						break;
					}
				
			if(regionToPlay!=-1){
				playersCardsAmountsWorstCase[i][regionToPlay]--;
				cardsTakenWorstCase--;
			}
		}		
		
		if(!taken)
			cardsTakenWorstCase=0.0;
		
		return takenCards + (takenCardFromOtherSuitProbability(thisCards,playersCardsAmountsBestCase,cardsTakenBestCase)+
				takenCardFromOtherSuitProbability(thisCards,playersCardsAmountsWorstCase,cardsTakenWorstCase))/2;
	}
	
	/**
	 * Calculates recursively the probable amount of cards taken in this distribution (if played a negative contract).
	 * Calculates recursively the average of the worst case and the best case.
	 * 
	 * @param cards Possession of cards.
	 * @param playersCardsAmounts Card amounts of all other players in all regions. 1st index is players, 2nd index is regions.
	 * @param takenCards Number of cards taken currently.
	 * @return Probable number of cards taken.
	 */
	private double takenCardProbability(boolean[] cards, int[][] playersCardsAmounts, double takenCards){		
		//finding the current lowest card
		boolean[] thisCards = ArrayOperations.copy(cards);
		
		int lowestCard;
		for(lowestCard=2;lowestCard<15;lowestCard++)
			if(thisCards[lowestCard])
				break;
		if(lowestCard==15)
			return takenCards;
		
		thisCards[lowestCard]=false;
		
		int[][] playersCardsAmountsBestCase = ArrayOperations.copy(playersCardsAmounts);
		int[][] playersCardsAmountsWorstCase = ArrayOperations.copy(playersCardsAmounts);
		boolean taken;
		
		//best case calculation
		double cardsTakenBestCase=0.0;
		taken=true;
		
		for(int i=0;i<3;i++)
			for(int j=0;j<playersCardsAmountsBestCase[0].length;j++)
				if(playersCardsAmountsBestCase[i][j]>0){
					if(emptyRegionsBeginWith[j]>lowestCard)
						taken=false;
						
					playersCardsAmountsBestCase[i][j]--;
					cardsTakenBestCase++;
					break;
				}
		
		//return if other players have no cards
		if(cardsTakenBestCase==0.0)
			return takenCards;
		
		if(taken){
			cardsTakenBestCase++;
			cardsTakenBestCase*=cardPossessionProbabilities[lowestCard];
		}	
		else
			cardsTakenBestCase=0.0;
		
		//worst case calculation
		double cardsTakenWorstCase=0.0;
		taken=true;
		int regionToPlay;
		
		for(int i=0;i<3;i++){
			regionToPlay=-1;
			for(int j=0;j<playersCardsAmountsWorstCase[0].length && emptyRegionsEndWith[j]<lowestCard;j++)
				if(playersCardsAmountsWorstCase[i][j]>0)
					regionToPlay=j;
			
			if(regionToPlay==-1)
				for(int j=playersCardsAmountsWorstCase[0].length-1;j>=0 && emptyRegionsBeginWith[j]>lowestCard;j--)
					if(playersCardsAmountsWorstCase[i][j]>0){
						taken=false;
						regionToPlay=j;
						break;
					}
				
			if(regionToPlay!=-1){
				playersCardsAmountsWorstCase[i][regionToPlay]--;
				cardsTakenWorstCase++;
			}
		}		
		
		if(taken){
			cardsTakenWorstCase++;
			cardsTakenWorstCase*=cardPossessionProbabilities[lowestCard];
		}
		else
			cardsTakenWorstCase=0.0;
		
		return takenCards + (takenCardProbability(thisCards,playersCardsAmountsBestCase,cardsTakenBestCase)+
				takenCardProbability(thisCards,playersCardsAmountsWorstCase,cardsTakenWorstCase))/2;
	}
	
	/**
	 * Calculates (taken cards in this situation) times (amount of this situation among all distributions) and adds it to its proper total probabilities.
	 * 
	 * @param playersCardsAmounts Matrix describing the situation of distribution of cards among 3 other players.1st index is players, 2nd index is empty regions
	 */
	private void addWeightedTakenCardAmountToTotalProbabilities(int[][] playersCardsAmounts){
		//amount of this situation among all distributions
		int subTotalSituations=1;
		
		//maximum card quantities in each region
		int[] regionsMaxQuantities = new int[playersCardsAmounts[0].length];
		for(int i=0;i<regionsMaxQuantities.length;i++)
			for(int j=0;j<3;j++)
				regionsMaxQuantities[i]+=playersCardsAmounts[j][i];
		
		for(int i=0;i<regionsMaxQuantities.length;i++)
			for(int j=0;j<3;j++){
				subTotalSituations*=Combinatorics.combination(regionsMaxQuantities[i],playersCardsAmounts[j][i]);
				regionsMaxQuantities[i]-=playersCardsAmounts[j][i];
			}
		
		//update the number of total situations
		totalSituations+=subTotalSituations;
		
		switch(calculationType){
			case TricksTakenFromThisSuit:
				probableAmountOfTakenTricks+=takenTrickProbability(cards,playersCardsAmounts,0)*subTotalSituations;
				
				double cardsOfPlayers_1[] = new double[3];
				for(int i=0;i<3;i++)
					for(int j=0;j<playersCardsAmounts[0].length;j++)
						cardsOfPlayers_1[i]+=playersCardsAmounts[i][j];
				//this suit will be played as much as the second greatest number of cards in the other 3 players
				probableAmountOfGivenTricks+=Misc.positivize(ArrayOperations.midElementOf(cardsOfPlayers_1)-cardsAmount)*subTotalSituations; 
				break;
			case CardsTakenFromAnotherSuit:
				probableAmountOfTakenCards+=takenCardFromOtherSuitProbability(cards,playersCardsAmounts,0)*subTotalSituations;
				
				double cardsOfPlayers_2[] = new double[3];
				for(int i=0;i<3;i++)
					for(int j=0;j<playersCardsAmounts[0].length;j++)
						cardsOfPlayers_2[i]+=playersCardsAmounts[i][j];
				//this suit will be played as much as the second greatest number of cards in the other 3 players
				probableAmountOfGivenCards+=Misc.positivize(ArrayOperations.midElementOf(cardsOfPlayers_2)-cardsAmount)*subTotalSituations; 
				break;
			case CardsTakenFromThisSuit:
				probableAmountOfTakenCards+=takenCardProbability(cards,playersCardsAmounts,0)*subTotalSituations;
				break;
		}
	}
	
	/**
	 * Generates all possible hand states of 3 other players for a given suit recursively; then calls the weighted probability calculator for each state.
	 * Cards in empty regions are identical.
	 * 
	 * @param playersCardsAmounts First index is player, second index is empty region number.
	 * @param player Current player.
	 * @param region Current region.
	 * @param playerCardAmounts Card amounts of players, decreased when cards are placed.
	 * @param emptyRegionCardAmounts Total card amounts in empty regions, decreased when cards are placed.
	 */
	private void generateHandStates(int[][] playersCardsAmounts, int player, int region, int[] playerCardAmounts, int[] emptyRegionCardAmounts){
		//last player is reached, place all remaining cards for this player in all regions
		if(player==2){
			//distribute all remaining cards to the last player.
			for(int i=0;i<emptyRegionCardAmounts.length;i++)
				playersCardsAmounts[2][i]+=emptyRegionCardAmounts[i];
			
			addWeightedTakenCardAmountToTotalProbabilities(playersCardsAmounts);
			
			//take back the distribution
			for(int i=0;i<emptyRegionCardAmounts.length;i++)
				playersCardsAmounts[2][i]-=emptyRegionCardAmounts[i];
			
			return;
		}
		
		//last region is reached, place all cards for this player in this region if possible, cancel everything if not possible
		if(region==emptyRegionCardAmounts.length-1){
			if(playerCardAmounts[player]>emptyRegionCardAmounts[region])//not possible to place all cards of this player in the last region
				return;
			
			//place all remaining cards of this player to the last region.
			playersCardsAmounts[player][region]+=playerCardAmounts[player];
			emptyRegionCardAmounts[region]-=playerCardAmounts[player];

			generateHandStates(playersCardsAmounts, player+1, 0, playerCardAmounts, emptyRegionCardAmounts);
			
			//take back this placement
			emptyRegionCardAmounts[region]+=playerCardAmounts[player];
			playersCardsAmounts[player][region]-=playerCardAmounts[player];
			
			return;
		}
		
		//pass to the next region without making any change to this player's this region
		generateHandStates(playersCardsAmounts,player,region+1,playerCardAmounts,emptyRegionCardAmounts);
		
		//add 1 card to this player's this region if it's allowed
		if(playerCardAmounts[player]>0 && emptyRegionCardAmounts[region]>0){
			//make the placement
			playerCardAmounts[player]--;
			emptyRegionCardAmounts[region]--;
			playersCardsAmounts[player][region]++;
			
			generateHandStates(playersCardsAmounts,player,region,playerCardAmounts,emptyRegionCardAmounts);
			
			//take back the placement
			playerCardAmounts[player]++;
			emptyRegionCardAmounts[region]++;	
			playersCardsAmounts[player][region]--;
		}
	}
	
	/**
	 * Calculates the probable taken card amount if only played with this suit.
	 * 
	 * Approaches other 3 players' hands as cards existing in empty regions.
	 * Empty regions are ranges of cards which this player does not possess.
	 * 
	 * Steps of calculation:
	 * 
	 * 1)Calculates the empty region quantity and card amounts in each empty region
	 * 
	 * 2)Calculates the number of cards which are possessed by other 3 players
	 * 
	 * 3)Generates every possible combination of hand states of other players by assuming cards in the same region are identical
	 * 
	 * 4)Calculates the sum of weighted probabilities of each hand state.
	 */
	public void calculate(){
		//check if there are no empty regions (all cards in hand)
		if(emptyRegionQuantity==0){
			probableAmountOfTakenTricks=13.0;
			probableAmountOfTakenCards=13.0;
			return;
		}
		
		//quantity of cards possessed by other players
		int cardsOut=0;
		for(int i=2;i<15;i++)
			if(!cards[i])
				cardsOut++;
		
		//other 3 players' card amounts in empty regions
		int[][] playersCardsAmounts;
		
		totalSituations=0;
		
		//generate every possible state
		int[] playerMaxCardAmounts = new int[3];
		for(playerMaxCardAmounts[0]=0;playerMaxCardAmounts[0]<=cardsOut;playerMaxCardAmounts[0]++)
			for(playerMaxCardAmounts[1]=playerMaxCardAmounts[0];playerMaxCardAmounts[1]<=(cardsOut-playerMaxCardAmounts[0])/2;playerMaxCardAmounts[1]++){
				playerMaxCardAmounts[2]=cardsOut-playerMaxCardAmounts[0]-playerMaxCardAmounts[1];	
				
				playersCardsAmounts = new int[3][emptyRegionQuantity];
				generateHandStates(playersCardsAmounts,0,0,playerMaxCardAmounts,emptyRegionCardQuantities);
			}
		
		switch(calculationType){
			case TricksTakenFromThisSuit:
				probableAmountOfTakenTricks/=totalSituations;
				probableAmountOfGivenTricks/=totalSituations;
				break;
			case CardsTakenFromAnotherSuit:
				probableAmountOfTakenCards/=totalSituations;
				probableAmountOfGivenCards/=totalSituations;
				break;
			case CardsTakenFromThisSuit:
				probableAmountOfTakenCards/=totalSituations;
				break;
		}
	}
}